package leetcode;

/**
 * 69.x的平方根
 * <p>
 * 二分法
 * x = 49 输出 7，x = 9 输出 3
 */
public class MySqrt {
    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        int res = -1;
        while (left < right) {
            int mid = (right + left) / 2;

            if ((long)mid * mid <= x) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
}
